package algorithm.sort;

import algorithm.sort.common.SortTestHelper;

/**
 * @author bingo
 * @Description   快速排序
 * @Date 2018/6/14
 */
public class QuickSort {

    public void sort(Comparable[] arr){
        _quickSort(arr,0,arr.length-1);
        }

    public void _quickSort(Comparable[] arr,int l,int r){
        if(l>=r){

            return;
         }
         int p = partition(arr,l,r);
        _quickSort(arr,l,p-1);
        _quickSort(arr,p+1,r);

    }

    private int partition(Comparable[] arr, int l, int r) {
        int j= l;
        Comparable v = arr[l];
        for(int i=l+1;i <= r;i++){
            if(arr[i].compareTo(v)<0){
                swap(arr,j+1,i);
                j++;
            }

        }
        swap(arr,l,j);
        return  j;
    }

    private void swap(Comparable[] arr,int j, int i) {

        Comparable temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        Comparable[] quickArr = SortTestHelper.generateRandomArray(50,0,10000);
        long start = System.currentTimeMillis();
        quickSort.sort(quickArr);
        long end = System.currentTimeMillis();
        System.out.println(SortTestHelper.isSorted(quickArr));
        System.out.println("快速排序耗时:"+(end-start)+"ms");
        SortTestHelper.printArray(quickArr);



    }
}
